/*

es_dungeonGen
-------------
This file contains the code required to generate a dungeon in cotw.  To use, simply
define an es_dungeonGen instance and call Generate().  More information on this
may be found below.

-- Ebonshadow

TODO:
	Add support for diagonal tunnels
	Add support for "vaults"
		vaults will be special rooms.  Some of these may just be odd shaped rooms
		to give variation to the map.  However, some of these will hold the key
		to the level.  For instance, level 4 in a dungeon could be preprogrammed
		to contain a particular vault somewhere.  This vault holds a boss mob, who
		drops a letter that takes him to another town.

Refer to the demo for usage.
*/

es_dungeonGen
	var
		z	// The z level that the dungeon generating will take place on

		x0	// Lower-left corner of the dungeon
		y0

		x1	// Upper-right corner of the dungon
		y1

		wall_type				// Used as the fill type for the dungeon
		tunnel_type				// Paths, etc..
		room_type				// Turf used for rooms.
		door_type				// When doors are created

		auto_expand = TRUE		// BOOL, expands the map if there isn't enough room

		// Rooms
		min_room_width  = 5				// min. width of room
		max_room_width  = 10			// max. width of room
		min_room_height	= 5	  		  	// min. height of room
		max_room_height	= 10	    	// max. height of room

		// Tunnels
		min_tunnel_length = 4
		max_tunnel_length = 10

		tunnel_prob = 60				// The probability that a new feature will be a tunnel
		room_prob	= 40				// ditto except for rooms
		door_prob	= 50				// the chance out of 100 when a path will be a door

		features	= 100				// Number of times to try to create features

		recurse		= 20				// Number of times to add extra doors for a "loop" affect on the map.
		diagonal_percent = 10			// Percentage of tunnels to be non-cardinal

	proc/Generate()		// Call this to generate the map

// Internal stuff.  Don't mess with this stuff.  If anything needs to be added/changed,
// email me at ebonshadow@byond.com

turf/var/es_isDiag

es_dungeonGen
	var
		turf/_corner0		// The dungeon corners
		turf/_corner1
		turf/_border0	// The dungeon corners with the border subtracted
		turf/_border1
	Generate(turf/start)
		if(!_Initialize()) return
		var/stairs
		stairs = _CreateFirstRoom(start)
		for(var/i = 1 to features)
			_AddFeature()
		if(recurse)
			for(var/i = 1 to recurse)
				_AddDoor()
		for(var/turf/t in block(_corner0, _corner1))
			for(var/es_tunnelend/e in t)
				e.expandtunnel()
				del e

		return stairs

	proc/_AddDoor()
		var/turf/t = _LocateWall()
		var/turf/north = get_step(t, NORTH)
		var/turf/south = get_step(t, SOUTH)
		var/turf/east  = get_step(t, EAST)
		var/turf/west  = get_step(t, WEST)
		var/usable = 0
		var/retry
		for(var/turf/t2 in list(north,south,east,west))
			if(istype(t2, door_type)) retry = 1
			if(t2.x >= _border1.x) retry = 1
			if(t2.y >= _border1.y) retry = 1
		// retry if there is a door nearby, stacked doors are ugly!
		if(retry)
			return .()
		if((istype(north, room_type)||istype(north, tunnel_type)) && (istype(south, room_type)||istype(south, tunnel_type)))
			usable = 1
		if((istype(east, room_type)||istype(east, tunnel_type)) && (istype(west, room_type)||istype(west, tunnel_type)))
			usable = 1
		if(usable)
			new tunnel_type (t)
	proc/_AddFeature()
		// This procedure is really the heart of the dungeon builder
		// It searches for a wall and adds a room or tunnel
		var/turf/loc0
		var/dir
		var/create_type
		var/success
		var/isroom
		// Find a suitable wall

		while(!loc0)
			var/turf/t = _LocateWall()
			for(var/turf/t2 in _Cardinal(t))
				if(istype(t2, tunnel_type)|| istype(t2, room_type))
					loc0 = t
					dir = get_dir(t2, t)
		create_type = pick(
						prob(tunnel_prob)
							tunnel_type,
						prob(room_prob)
							room_type)
		if(create_type==tunnel_type)
			success = _CreateTunnel(loc0, dir)
		else
			success = _CreateRoom(loc0, dir)
		if(!success) return 0
		for(var/turf/t in _Cardinal(loc0))
			if(istype(t, room_type))
				isroom = 1
				break
		if(isroom && rand(1,100) <= door_prob)
			new door_type (loc0)
		else
			new tunnel_type (loc0)
		return 1

	proc/_LocateTunnel()
		while(1)
			var/turf/t = locate(rand(_border0.x, _border1.x), rand(_border0.y, _border1.y), z)
			if(istype(t, tunnel_type)) return t
	proc/_LocateRoom()
		while(1)
			var/turf/t = locate(rand(_border0.x, _border1.x), rand(_border0.y, _border1.y), z)
			if(istype(t, room_type)) return t
	proc/_Cardinal(turf/loc0)
		return list(get_step(loc0, NORTH),get_step(loc0, SOUTH),get_step(loc0, EAST),get_step(loc0, WEST))
	proc/_LocateWall()
		while(1)
			var/turf/t = locate(rand(_border0.x, _border1.x), rand(_border0.y, _border1.y), z)
			if(istype(t, wall_type)) return t
	proc/_CreateFirstRoom(start)
		if(start)
			while(1)
				var/turf/t = _CreateRoom(start)
				if(t) return t
		while(1)
			var/turf/loc0 = _LocateWall()
			var/turf/t = _CreateRoom(loc0)
			if(t) return t
		return 0

	proc/_CreateRoom(turf/loc0, dir)
		if(!dir) dir = pick(NORTH,SOUTH,EAST,WEST)
		var/width = rand(min_room_width, max_room_width)
		var/height = rand(min_room_height, max_room_height)

		switch(dir)
			if(NORTH) loc0 = locate(loc0.x-rand(1,round(width/2)), loc0.y, z)
			if(SOUTH) loc0 = locate(loc0.x-rand(1,round(width/2)), loc0.y-height, z)
			if(EAST)  loc0 = locate(loc0.x, loc0.y-rand(1,round(height/2)), z)
			if(WEST)  loc0 = locate(loc0.x-width, loc0.y-rand(1,round(height/2)), z)
		if(_FillRect(loc0, height, width, room_type))
			var/turf/t = pick(block(loc0, locate(loc0.x+width-1, loc0.y+height-1, loc0.z)))
			return t

	proc/_CreateTunnel(turf/loc0, dir)
		var/length = rand(min_tunnel_length, max_tunnel_length)
		var/origdir = dir
		if(rand(1,100)<=diagonal_percent)
			if(dir == NORTH) 		dir = pick(NORTHEAST, NORTHWEST)
			else if(dir == EAST)  	dir = pick(NORTHEAST, SOUTHEAST)
			else if(dir == SOUTH)	dir = pick(SOUTHEAST, SOUTHWEST)
			else if(dir == WEST)	dir = pick(NORTHWEST, SOUTHWEST)
		switch(dir)
			if(NORTH) if(_FillRect(get_step(loc0, NORTH), length, 1, tunnel_type)) return 1
			if(SOUTH) if(_FillRect(locate(loc0.x, loc0.y-length, z), length, 1, tunnel_type)) return 1
			if(EAST)  if(_FillRect(get_step(loc0, EAST), 1, length, tunnel_type)) return 1
			if(WEST)  if(_FillRect(locate(loc0.x-length, loc0.y, z), 1, length, tunnel_type)) return 1

			// Diagonals
			if(NORTHEAST) if(_FillDiag(get_step(loc0, origdir), length, NORTHEAST, tunnel_type)) return 1
			if(NORTHWEST) if(_FillDiag(get_step(loc0, origdir), length, NORTHWEST, tunnel_type)) return 1
			if(SOUTHEAST) if(_FillDiag(get_step(loc0, origdir), length, SOUTHEAST, tunnel_type)) return 1
			if(SOUTHWEST) if(_FillDiag(get_step(loc0, origdir), length, SOUTHWEST, tunnel_type)) return 1
	proc/_FillDiag(turf/loc0, length, dir, fill_type)
		if(!loc0) return 0
		if(!_IsClearDiag(loc0, length, dir)) return 0
		var/top
		var/bot
		if(dir == NORTHEAST||dir == SOUTHWEST)
			top = "corner1"
			bot = "corner4"
		else
			top = "corner2"
			bot = "corner3"
		var/i
		for(var/turf/t in _GetDiag(loc0, length, dir))
			i ++
			var/turf/t2 = get_step(t, NORTH)
			var/turf/t3 = get_step(t, SOUTH)
			new fill_type (t)
			new wall_type (t2)
			new wall_type (t3)
			if(i==1)
				if(dir == NORTHEAST || dir == NORTHWEST)
					t2.icon_state = top
					t2.opacity = 0
					t2.es_isDiag = 1
				if(dir == SOUTHWEST || dir == SOUTHEAST)
					t3.icon_state = bot
					t3.opacity = 0
					t3.es_isDiag = 1
			else if(i==length)
				if(dir == SOUTHWEST || dir == SOUTHEAST)
					t2.icon_state = top
					t2.opacity = 0
					t2.es_isDiag = 1
				if(dir == NORTHEAST || dir == NORTHWEST)
					t3.icon_state = bot
					t3.opacity = 0
					t3.es_isDiag = 1
			else
				t2.icon_state = top
				t2.opacity = 0
				t2.es_isDiag = 1
				t3.icon_state = bot
				t3.opacity = 0
				t3.es_isDiag = 1

		return 1

	proc/_GetDiag(turf/loc0, length, dir)
		var/list/l = list()
		for(var/i = 1 to length)
			l += loc0
			loc0 = get_step(loc0, dir)
		return l

	proc/_IsClearDiag(turf/loc0, length, dir)
		for(var/i = 1 to length)
			var/list/l = list(loc0, get_step(loc0, NORTH), get_step(loc0, SOUTH))
			for(var/turf/t in l)
				if(!istype(t, wall_type)) return 0
				if(t && t.es_isDiag) return 0
			loc0 = get_step(loc0, dir)
			if(!loc0) return 0
		return 1

	proc/_FillRect(turf/loc0, height, width, fill_type)
		// First check to see if the area is clear.
		if(!loc0) return 0
		var/turf/border0 = locate(loc0.x-1, loc0.y-1, loc0.z)
		var/turf/border1 = locate(loc0.x+width, loc0.y+height, loc0.z)
		var/turf/corner0 = loc0
		var/turf/corner1 = locate(loc0.x + (width-1), loc0.y + (height - 1), loc0.z)
		if(!_IsClearRectangle(border0,border1))
			return 0
		for(var/turf/t in block(corner0, corner1))
			new fill_type (t)
		if(fill_type==tunnel_type)
			new /es_tunnelend (corner0, get_dir(corner1, corner0), src)
			new /es_tunnelend (corner1, get_dir(corner0, corner1), src)
		return 1
	proc/_IsClearRectangle(turf/loc0, turf/loc1)
		if(!loc0 || !loc1) return 0
		for(var/turf/t in block(loc0, loc1))
			if(!istype(t, wall_type)) return 0
			if(t && t.es_isDiag) return 0
		return 1
	proc/_Initialize()
		// Check to make sure there is room for the dungeon.
		if(auto_expand)
			if(z  > world.maxz) world.maxz = z
			if(x1 > world.maxx) world.maxx = x1
			if(y1 > world.maxy) world.maxy = y1
		_corner0 = locate(x0,y0,z)
		_corner1 = locate(x1,y1,z)
		if(!_corner0||!_corner1)
			// one of the corners does exist.
			CRASH("es_dungeonGen:  Dungeon corner out of map boundries!")
		if(!ispath(wall_type))
			CRASH("es_dungeonGen:  wall_type invalid.")
		if(!ispath(tunnel_type))
			CRASH("es_dungeonGen:  tunnel_type invalid.")
		if(!ispath(room_type))
			CRASH("es_dungeonGen:  room_type invalid.")
		if(!ispath(door_type))
			CRASH("es_dungeonGen:  door_type invalid.")

		for(var/turf/t in block(_corner0, _corner1))
			new wall_type (t)

		// Set the borders of the map.
		_border0 = locate(x0+1, y0+1, z)
		_border1 = locate(x1-1, y1-1, z)
		return 1

// Used to designate tunnel ends so that dead ends can be removed
es_tunnelend
	parent_type = /atom/movable
	icon = 'espath.dmi'
	icon_state = "tunnelend"
	var/es_dungeonGen/owner
	New(Loc, Dir, es_dungeonGen/Owner)
		dir = Dir
		owner = Owner
		return ..()
	proc/expandtunnel()
		if(!_isdeadend()) return
		var/turf/t0 = loc
		var/turf/t1
		var/turf/t2
		var/found
		for()
			t1 = get_step(t0, dir)
			if(t1==t0) return 0
			t0 = t1
			if(!istype(t1, owner.wall_type))
				if(istype(t1,owner.tunnel_type)) break
				if(istype(t1,owner.room_type)) break
				else return 0
			// Check to see if any of the cardinal turfs are clear, if so, we can stop here.
			found = 0
			for(t2 in list(get_step(t1,turn(dir,90)),get_step(t1,turn(dir,-90))))
				if(istype(t2,owner.tunnel_type)||istype(t2,owner.room_type))
					t0 = get_step(t0, dir)
					found =1
					break
			if(found) break
		for(t1 in block(loc, t0))
			if(t1 == t0) continue
			if(t1 == loc) continue
			new owner.tunnel_type(t1)
			t1.overlays += icon('combat.dmi', icon_state="combat square")
		return 1
	proc/_isdeadend()
		var/turf/t = get_step(src, dir)
		if(!istype(t, owner.tunnel_type)) return 1